제3장. 양자 푸리에 변환과 위상 추정

2장에서 우리는 양자 병렬성을 이용해 \(f(x)\)의 ‘전역적 속성’(상수인가 균형인가)을 찾는 법을 배웠습니다. 하지만 양자컴퓨터의 진정한 힘은 \(f(x)\)의 주기성(Periodicity)을 찾는 데 있으며, 이는 4장에서 배울 쇼어의 소인수분해 알고리즘의 핵심입니다.

주기성을 찾는 가장 강력한 수학적 도구는 푸리에 변환(Fourier Transform)입니다. 이 장에서는 고전적인 푸리에 변환을 양자화한 양자 푸리에 변환(QFT)을 소개합니다. QFT는 고전적인 대응물(FFT)보다 지수적으로 빠르며, 그 자체로 양자 위상 추정(Phase Estimation)이라는 강력한 알고리즘의 핵심 엔진으로 작동합니다.

1. 기본 개념 (Fundamental Concepts)

  • 이산 푸리에 변환 (DFT): 고전적인 DFT는 \(N\)개의 데이터 점(신호) \(x_0, \dots, x_{N-1}\)을 입력받아, 이 신호를 구성하는 \(N\)개의 주파수(진폭) \(y_0, \dots, y_{N-1}\)로 변환하는 작업입니다. \[y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j e^{2\pi i jk / N}\] 이는 ‘시간’ 영역의 정보를 ‘주파수’ 영역의 정보로 바꾸는 것입니다.

  • 양자 푸리에 변환 (QFT): QFT는 DFT의 양자적 버전입니다. 이는 \(N=2^n\)개의 계산 기저 상태(computational basis)를 푸리에 기저(Fourier basis)라는 새로운 기저로 변환하는 유니터리 변환입니다. \[\text{QFT} |x\rangle = \frac{1}{\sqrt{N}}\sum_{y=0}^{N-1} e^{2\pi i xy / N} |y\rangle\]

    • 의미: \(|x\rangle\)라는 단일 상태(시간 ‘x’에서의 ’틱’)를, 모든 \(y\) 주파수 성분이 중첩된 상태로 변환합니다.

  • QFT의 효율성: 고전적으로 \(N\)개의 점을 DFT하는 가장 빠른 방법(FFT)은 약 \(O(N \log N)\)의 연산이 필요합니다. \(N=2^n\)이므로 이는 \(O(n 2^n)\)로, \(n\)에 대해 지수적입니다. 양자 회로를 이용한 QFT는 단 \(O(n^2)\)개의 게이트만으로 구현할 수 있습니다. 이는 지수적 속도 향상(exponential speedup)입니다.

  • QFT 회로: QFT는 단일 게이트가 아니라, 1장에서 배운 하다마드(H) 게이트와 제어-회전(Controlled-Rotation) 게이트의 조합으로 구성됩니다.

    • \(R_k\) 게이트: \(R_k = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i / 2^k} \end{pmatrix}\) (Z축 기준 \(2\pi/2^k\) 라디안 회전)

  • 양자 위상 추정 (Quantum Phase Estimation, QPE): QFT의 가장 강력한 응용입니다. 어떤 유니터리 연산자 \(U\)와 그 고유 상태 \(|\psi\rangle\)가 주어졌을 때, \(U|\psi\rangle = e^{2\pi i \phi} |\psi\rangle\)를 만족하는 고유값의 위상(phase) \(\phi\)를 찾아내는 알고리즘입니다.

  • 역 QFT (Inverse QFT, QFT\(^\dagger\)): QFT는 유니터리 변환이므로, 그 역변환(\(\text{QFT}^\dagger\))이 존재합니다. 이는 푸리에 기저(주파수)를 다시 계산 기저(시간/값)로 되돌립니다. 위상 추정 알고리즘은 QFT가 아닌 역 QFT를 사용하여 최종 답을 읽어냅니다.

2. 기호 및 핵심 관계식

  • QFT (정의): \(N=2^n\) \[\text{QFT}_{N} : |x\rangle \mapsto \frac{1}{\sqrt{N}}\sum_{y=0}^{N-1} \omega_N^{xy} |y\rangle \quad (\text{단, } \omega_N = e^{2\pi i / N})\]

  • QFT (회로를 위한 곱 분해): \(n\)-큐빗 상태 \(|x\rangle = |x_1 x_2 \dots x_n\rangle\) (이진수 \(x_j \in \{0, 1\}\))에 대한 QFT는 다음과 같이 아름답게 분해됩니다. ( \(0.x_k x_{k+1} \dots\)는 이진 소수) \[\text{QFT}|x\rangle = \frac{1}{\sqrt{2^n}} \left( |0\rangle + e^{2\pi i 0.x_n} |1\rangle \right) \otimes \left( |0\rangle + e^{2\pi i 0.x_{n-1}x_n} |1\rangle \right) \otimes \dots \otimes \left( |0\rangle + e^{2\pi i 0.x_1 x_2 \dots x_n} |1\rangle \right)\]

  • 위상 추정 (QPE)의 핵심:

    • 입력: \(n\)개의 카운팅 큐빗 \(|0\rangle^{\otimes n}\)과, \(U\)의 고유 상태 \(|\psi\rangle\).
    • 중간 상태 (제어-U 연산 후): \(H^{\otimes n}|0\rangle^{\otimes n} |\psi\rangle \to \frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1} |k\rangle |\psi\rangle\) \(\xrightarrow{C-U^{2^k} \text{ 적용}} \frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1} U^k |k\rangle |\psi\rangle = \frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1} (e^{2\pi i \phi})^k |k\rangle |\psi\rangle\) \[= \left( \frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1} e^{2\pi i \phi k} |k\rangle \right) \otimes |\psi\rangle\]
    • 최종 상태 (역 QFT 적용 후): 위 중간 상태의 카운팅 레지스터에 \(\text{QFT}^\dagger\)를 적용하면, \[|\tilde{\phi}\rangle \otimes |\psi\rangle \quad (\text{단, } |\tilde{\phi}\rangle \text{는 } \phi \text{를 } n\text{비트로 근사한 값})\]

3. 손쉬운 예제 (Examples with Deeper Insight)

예제 1: QFT의 의미 (n=2, N=4)

  • 질문: QFT는 ’주파수’로 변환한다는데, 그게 무슨 뜻인가요?

  • 답: QFT는 ’시간 축’의 상태를 ’주파수 축’의 상태로 바꿉니다.

  • 상황: \(N=4\) (\(n=2\)) 시스템, \(\omega = e^{2\pi i / 4} = i\).

    • \(|0\rangle \equiv |00\rangle\): “틱 0”
    • \(|1\rangle \equiv |01\rangle\): “틱 1”
    • \(|2\rangle \equiv |10\rangle\): “틱 2”
    • \(|3\rangle \equiv |11\rangle\): “틱 3”

  • 계산: \(\text{QFT}|1\rangle = \frac{1}{\sqrt{4}}\sum_{y=0}^{3} \omega^{1\cdot y} |y\rangle = \frac{1}{2}( \omega^0|0\rangle + \omega^1|1\rangle + \omega^2|2\rangle + \omega^3|3\rangle )\) \(= \frac{1}{2}( |0\rangle + i|1\rangle + i^2|2\rangle + i^3|3\rangle ) = \frac{1}{2}( |0\rangle + i|1\rangle - |2\rangle - i|3\rangle )\)

  • 💡 상세 설명 (주파수 인코딩):

    “틱 1”(\(|1\rangle\)) 상태는 주파수 0, 1, 2, 3 성분을 모두 가진 것처럼 보입니다. 하지만 이 계수 \((1, i, -1, -i)\)를 잘 보세요. 이는 \(y=0 \to 3\)으로 가면서 위상이 \(0^\circ \to 90^\circ \to 180^\circ \to 270^\circ\) 로 \(1/4\)씩 (즉, 주파수 ‘1’) 일정하게 증가하는 것을 의미합니다. 반면, \(\text{QFT}|0\rangle = \frac{1}{2}(|0\rangle + |1\rangle + |2\rangle + |3\rangle)\) 입니다.

    • QFT \(|0\rangle\): 주파수 0 (DC 성분)을 의미합니다. 위상 변화가 없습니다.
    • QFT \(|1\rangle\): 주파수 1 (1/4 주기)을 의미합니다. 위상이 \(i\)배씩 변합니다.
    • QFT \(|2\rangle\): 주파수 2 (2/4 주기)를 의미합니다. 위상이 \(-1\)배씩 변합니다.
    • QFT \(|3\rangle\): 주파수 3 (3/4 주기)을 의미합니다. 위상이 \(-i\)배씩 변합니다.

    즉, QFT는 계산 기저 \(|x\rangle\)를, 주파수 \(x\)에 해당하는 위상 중첩 상태로 변환합니다.

예제 2: QFT 회로 (n=3, \(N=8\))

  • 상황: \(n=3\) 큐빗 QFT 회로를 구성합니다. \(R_k\)는 큐빗 \(j, k\) 사이에 \(C-R_{j-k}\) 게이트를 의미합니다.

  • 회로도:

    \(|x_1\rangle \longrightarrow [H] \--- [R_2] \--- [R_3] \--- \text{SWAP} \longrightarrow |\tilde{x}_3\rangle\) \(|x_2\rangle \longrightarrow \quad \quad [H] \--- [R_2] \--- \text{SWAP} \longrightarrow |\tilde{x}_2\rangle\) \(|x_3\rangle \longrightarrow \quad \quad \quad \quad [H] \--- \quad \quad \quad \longrightarrow |\tilde{x}_1\rangle\)

  • 💡 상세 설명 (회로가 작동하는 법과 \(O(n^2)\) 효율):

    위 곱 분해 공식(\(\text{QFT}|x\rangle \propto \dots \otimes (|0\rangle + e^{2\pi i 0.x_1 x_2 x_n} |1\rangle)\))을 거꾸로 읽어봅시다.

    1. 가장 밑 큐빗(\(|\tilde{x}_1\rangle\) 생성): 맨 밑줄은 \(\frac{1}{\sqrt{2}}(|0\rangle + e^{2\pi i 0.x_1 x_2 x_3} |1\rangle)\)가 되어야 합니다. (이진 소수 \(0.x_1 x_2 x_3 = x_1/2 + x_2/4 + x_3/8\))
    • \(x_1\)은 \(R_2\)(\(\pi/2\)) 회전, \(x_2\)는 \(R_3\)(\(\pi/4\)) 회전, \(x_3\)는 \(R_4\)(\(\pi/8\)) 회전… 아, 곱 분해 공식의 맨 마지막 항이네요!
    1. 가장 위 큐빗(\(|\tilde{x}_3\rangle\) 생성): 맨 윗줄은 \(\frac{1}{\sqrt{2}}(|0\rangle + e^{2\pi i 0.x_3} |1\rangle)\)가 되어야 합니다.
    • \(H\) 게이트를 \(|x_3\rangle\)에 적용하면 \(\frac{1}{\sqrt{2}}(|0\rangle + (-1)^{x_3}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + e^{i\pi x_3}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + e^{2\pi i 0.x_3}|1\rangle)\) 가 됩니다. (이진 소수 \(0.x_3 = x_3/2\))
    • 이것이 곱 분해 공식의 첫 번째 항입니다.
    1. 효율성: 회로를 잘 보면, 1번 큐빗은 \(H\)와 \((n-1)\)개의 C-ROT 게이트, 2번 큐빗은 \(H\)와 \((n-2)\)개의 게이트, …, \(n\)번 큐빗은 \(H\) 게이트 1개만 필요합니다. 총 게이트 수는 \(n + (n-1) + \dots + 1 = n(n+1)/2\) 입니다. (SWAP 제외 시) 이는 \(O(n^2)\)입니다. \(n=1000\)일 때, 고전 FFT는 \(\approx 1000 \cdot 2^{1000}\) (불가능)이지만, QFT는 \(\approx 1000^2 / 2 = 500,000\) (매우 빠름)개의 게이트만 필요합니다.

예제 3: 위상 추정 (QPE) - T 게이트의 위상 찾기

  • 문제: \(T\) 게이트(\(T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix}\))의 고유 상태 \(|1\rangle\)이 있습니다. \(T|1\rangle = e^{i\pi/4}|1\rangle = e^{2\pi i (1/8)}|1\rangle\) 이므로, \(\phi = 1/8\) 입니다. QPE를 이용해 \(\phi=1/8\) (이진수 0.001)을 \(n=3\) 비트 정밀도로 찾아봅시다.
  • 회로: 3개의 카운팅 큐빗 \(|000\rangle\)과 대상 큐빗 \(|1\rangle\)을 준비합니다.
  • 계산 (단계별):
    1. H 게이트: 카운팅 큐빗 \(\to \frac{1}{\sqrt{8}}\sum_{k=0}^{7} |k\rangle\).
    2. 제어-U 연산:
      • \(k=1\) (\(|001\rangle\))이면: \(C-T^{2^0} = C-T^1\) 적용 \(\to e^{2\pi i \phi \cdot 1}\) 위상
      • \(k=2\) (\(|010\rangle\))이면: \(C-T^{2^1} = C-T^2\) 적용 \(\to e^{2\pi i \phi \cdot 2}\) 위상
      • …
      • \(k\)이면: \(\to e^{2\pi i \phi k}\) 위상
    3. 중간 상태: \(\left( \frac{1}{\sqrt{8}}\sum_{k=0}^{7} e^{2\pi i \phi k} |k\rangle \right) \otimes |1\rangle\)
    4. \(\phi = 1/8\) 대입: \(\left( \frac{1}{\sqrt{8}}\sum_{k=0}^{7} e^{2\pi i (k/8)} |k\rangle \right) \otimes |1\rangle\)
    5. 역 QFT 적용: QFT의 정의 \(\text{QFT}|x\rangle = \frac{1}{\sqrt{N}}\sum_y e^{2\pi i xy/N} |y\rangle\)를 봅시다. 만약 \(x=1\)을 넣으면, \(\text{QFT}|1\rangle = \frac{1}{\sqrt{8}}\sum_k e^{2\pi i (k/8)} |k\rangle\) 입니다. 이것이 정확히 4번 단계의 괄호 안 상태와 같습니다! 따라서 이 상태에 \(\text{QFT}^\dagger\) (역변환)을 적용하면, \(\text{QFT}^\dagger \left( \frac{1}{\sqrt{8}}\sum_{k=0}^{7} e^{2\pi i (k/8)} |k\rangle \right) = |1\rangle = |001\rangle\)
  • 💡 상세 설명 (측정): > 카운팅 레지스터를 측정하면 항상 \(|001\rangle\)이 나옵니다. > 이진수 \(001\)을 소수점으로 읽으면 \(0.001_2\) 이며, > \(0.001_2 = 0 \cdot \frac{1}{2} + 0 \cdot \frac{1}{4} + 1 \cdot \frac{1}{8} = 1/8\) 입니다. > 우리는 QPE를 통해 \(T\) 게이트의 위상 \(\phi=1/8\)을 정확하게 찾아냈습니다!

4. 연습문제

  1. QFT (n=2): \(n=2\) (N=4) 시스템에서 \(\text{QFT}|00\rangle\)의 결과를 계산하고, 예제 1의 \(\text{QFT}|0\rangle\)과 비교하십시오.
  2. QFT (n=2): \(\text{QFT}|10\rangle\) (즉, \(\text{QFT}|2\rangle\))를 계산하십시오.
  3. QFT 회로 (n=2): 2-큐빗 QFT 회로를 (예제 2처럼) 그리고, 총 몇 개의 게이트가 필요한지 세어보십시오. (SWAP 포함)
  4. QPE (S 게이트): \(S\) 게이트(\(S|1\rangle = i|1\rangle\))의 위상 \(\phi\)는 얼마입니까? (\(e^{2\pi i \phi}\) 꼴로) \(n=2\) 비트 QPE로 이 \(\phi\)를 찾는다면, 측정 결과(이진수)는 무엇이겠습니까?
  5. QPE (비-정확): 만약 \(\phi = 1/3\) 이고 \(n=3\) 비트로 QPE를 수행한다면, 측정 결과는 어떻게 나올지 예측해보십시오.

5. 해설

  1. \(\text{QFT}|00\rangle = \text{QFT}|0\rangle = \frac{1}{\sqrt{4}}\sum_{y=0}^{3} e^{2\pi i (0\cdot y) / 4} |y\rangle = \frac{1}{2}\sum |y\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle + |11\rangle)\). 이는 예제 1의 \(\text{QFT}|0\rangle\)과 같습니다.
  2. \(\text{QFT}|10\rangle = \text{QFT}|2\rangle = \frac{1}{2}\sum_{y=0}^{3} e^{2\pi i (2y) / 4} |y\rangle = \frac{1}{2}\sum_{y=0}^{3} e^{\pi i y} |y\rangle\) \(= \frac{1}{2}(|0\rangle + e^{\pi i}|1\rangle + e^{2\pi i}|2\rangle + e^{3\pi i}|3\rangle) = \frac{1}{2}(|0\rangle - |1\rangle + |2\rangle - |3\rangle)\).
  3. 회로: \(|x_1\rangle \to [H] \to [R_2] \to \text{SWAP}\) \(|x_2\rangle \to \quad \quad [H] \to \text{SWAP}\) 총 4개의 게이트 (H 2개, \(C-R_2\) 1개, SWAP 1개)가 필요합니다.
  4. \(S|1\rangle = i|1\rangle = e^{i\pi/2}|1\rangle = e^{2\pi i (1/4)}|1\rangle\). 따라서 \(\phi = 1/4\) 입니다. \(n=2\) 비트로 인코딩하면 \(\phi = 0.01_2\) (\(0 \cdot \frac{1}{2} + 1 \cdot \frac{1}{4} = 1/4\)). 측정 결과는 \(|01\rangle\) 입니다.
  5. \(\phi = 1/3 \approx 0.010101\dots_2\). \(n=3\) 비트로 측정하면 \(0.010_2 (= 2/8 = 1/4)\) 또는 \(0.011_2 (= 3/8)\) 근처의 값이 확률적으로 나옵니다. \(\phi\)가 \(n\)비트 이진수로 정확히 표현되지 않기 때문에, 측정 결과는 \(\phi\)에 가장 가까운 이진수 값들 주변으로 확률 분포를 보입니다.